package com.learn.arr;

/**
 * 求解小于某数的子数组和的最长长度
 *
 * @Author: huangzhigao
 * @Date: 2022/2/8 21:26
 */
public class LongestLessSumSubArr {
    public int getLength(int[] arr, int k) {
        int N = arr.length;

        int[] minSumArr = new int[N];
        int[] minSumEnd = new int[N];
        minSumArr[N - 1] = arr[N - 1];
        minSumEnd[N - 1] = N - 1;
        //以i位置开始向右扩，最小和的范围
        for (int i = N - 2; i >= 0; i--) {
            if (minSumArr[i + 1] <= 0) {
                minSumArr[i] = arr[i] + minSumArr[i + 1];
                minSumEnd[i] = minSumEnd[i + 1];
            } else {
                minSumArr[i] = arr[i];
                minSumEnd[i] = i;
            }
        }


        int sum = 0;
        int len = 0;
        int end = 0;

        for (int i = 0; i < N; i++) {
            while (end < arr.length && sum + minSumArr[end] <= k) {
                sum += minSumArr[end];
                end = minSumEnd[end] + 1;
            }

            len = Math.max(end - i, len);

            if (end > i) {
                sum -= arr[i];
            } else {
                end = i + 1;
            }
        }

        return len;
    }
}
